package com.congee02.sw.var;

import java.util.*;

public class LengthOfLongestSubstring {

    public int lengthOfLongestSubstring(String s) {

        if (s.isEmpty()) {
            return 0;
        }

        char[] cs = s.toCharArray();
        int n = cs.length;

        int[] rightest = new int[128];
        Arrays.fill(rightest, -1);

        // 初始化窗口: l = r = 0
        int ans = 1;
        rightest[cs[0]] = 0;
        int size = 1;

        // 从 l = 0, r = 1 开始
        int l = 0;
        for (int r = 1 ; r < n ; r ++ ) {
            // 先加入元素，然后检查是否符合条件
            if (rightest[cs[r]] == -1) {
                size ++;
            }
            rightest[cs[r]] = r;
            // 不符合则右移左边界直至满足条件
            while (size != r - l + 1) {
                if (rightest[cs[l]] <= l) {
                    rightest[cs[l]] = -1;
                    size --;
                }
                l ++;
            }
            // 此时已经满足条件
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }

}
